/*
字符串匹配：
	已知两字符串s、t，t是否为s的子串，如果是，返回位置。
*/

#include<iostream>
#include<string>
using namespace std;

// 记录比较次数
int cnt=0;

// 字符串匹配
int BF(string s, string t)
{
	// 指向两个字符串的指针
	int i=0, j=0;
	
	while (i<s.length() && j<t.length())
	{
		cnt++;
		
		// 比较的两个字符相同时，两指针向后移
		if (s[i]==t[j])
		{
			i++;
			j++;
		}
		
		// 比较的两个字符不相同时，从下一个位置开始匹配
		else
		{
			// i回退到原i的下一个位置
			i=i-j+1;	
			
			//j从0开始
			j=0;	
		}
	}
	
	// 匹配成功
	if (j==t.length())
		return i-j;	 // t是s的子串,返回位置
		
	// 匹配失败
	else
		return -1;
}


int main()
{
	// 两个字符串
	string s="aaaabc";
	string t="aab";
	
	// 打印匹配结果
	printf("%d\n", BF(s,t));
	
	// 打印比较次数
	printf("cnt=%d\n",cnt);
	return 0;
}
